# 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
# k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
# 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
#
#  示例 1：
# 输入：head = [1,2,3,4,5], k = 2
# 输出：[2,1,4,3,5]
#
#  示例 2：
# 输入：head = [1,2,3,4,5], k = 3
# 输出：[3,2,1,4,5]
#
from typing import Optional
from com.example.linked.common import *


class Solution:
    """
        完成链表从 startNode 开始到 endNode 结束（不包含 endNode）的反转
    """

    def reverseGroup(self, startNode: Optional[ListNode], endNode: Optional[ListNode]) -> None:
        last = startNode
        startNode = startNode.next
        while startNode != endNode:
            # 因为最后需要移动到下一个节点进行遍历，所以临时保存一下 head.next
            nextHead = startNode.next
            # 这两步完成反转操作
            startNode.next = last
            last = startNode
            # 遍历下一个节点
            startNode = nextHead

    """
            1.分组（往后走 k - 1 步，找到一组）
            2.一组内部完成反转
            3.更新每组跟前一组、后一组的边
    """

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        protect = ListNode(0, head)
        last = protect
        while head:
            # 1.分组（往后走 k - 1 步，找到一组）
            groupEndNode = self.getGroupEnd(head, k)
            if not groupEndNode:
                break

            nextGroupHead = groupEndNode.next
            # 2.一组内部完成反转
            self.reverseGroup(head, nextGroupHead)

            # 3.更新每组跟前一组、后一组的边
            last.next = groupEndNode
            head.next = nextGroupHead

            last = head
            head = nextGroupHead

        return protect.next

    def getGroupEnd(self, startNode: Optional[ListNode], k: int) -> Optional[ListNode]:
        while startNode:
            k -= 1
            if k == 0:
                return startNode
            startNode = startNode.next
        return startNode


if __name__ == "__main__":
    l = getListNode(2, 4, 6, 1, 2)
    res = Solution().reverseKGroup(l, 2)
    vistListNode(res)
